//
// Created by Hello on 2024/2/11.
//  线索化二叉树
#include <iostream>
#include <stack>

using namespace std;
// 线索二叉树结点类型
struct BthNode
{
    char data;          // 存放结点值
    BthNode* lchild, *rchild;   // 左右孩子或线索的指针
    int ltag, rtag;     // 左右标记

    BthNode(){}     // 构造函数
    BthNode(char d)
    {
        data = d;
        ltag = rtag = 0;
        lchild = rchild = nullptr;
    }
};
// 中序线索二叉树类
class ThreadTree
{
    BthNode* r;     // 二叉树的根结点指针
    BthNode* root;  // 线索二叉树的头结点指针
    BthNode* pre;   // 用于中序线索化，指向中序前驱结点
public:
    ThreadTree() {  // 构造函数，用于初始化
        r = nullptr;    // 初始化二叉树为空树
        root = nullptr; // 初始化线索二叉树为空树
    }
    ~ThreadTree() { // 析构函数，用于释放线索二叉树的所有节点
        if(r != nullptr)
            DestroyBTree1(r);   // 释放原二叉树中所有结点
        if(root != nullptr)
            delete root;    // 释放头结点
    }
    // 释放原二叉树的所有结点
    void DestroyBTree1(BthNode* b)
    {
        if(b->ltag == 0)
            DestroyBTree1(b->lchild);
        if(b->rtag == 0)
            DestroyBTree1(b->rchild);
        delete b;
    }
    //====二叉树的基本操作(结点类型改为BthNode)
    void CreateBTree(string str)
    // 创建以r为根结点的二叉链存储结构
    {

    }
    void DispBTree();               // 输出二叉树的括号表示串
    //====中序线索二叉树的基本操作
    // 建立以root为头结点的中序线索二叉树
    void CreateThread()
    {
        root = new BthNode();   // 创建头结点root
        root->ltag = 0;
        root->rtag = 1; // 头结点域置初值
        root->rchild = r;

        if(r == nullptr)    // r为空树时
        {
            root->lchild = root;
            root->rchild = nullptr;
        }
        else    // r不为空树时
        {
            root->lchild = r;
            pre = root;         // pre指向结点p的前驱结点，供加线索用
            Thread(r);          // 中序遍历线索化二叉树
            pre->rchild = root; // 最后处理，加入指向根结点的线索
            pre->rtag = 1;
            root->rchild = pre; // 头结点线索化
        }
    }
    //对结点p的二叉树中序线索化
    void Thread(BthNode* &p)
    {
        if(p != nullptr)
        {
            Thread(p->lchild);  // 左子树线索化

            // 建立pre和p之间的线索：相当于中序遍历中访问根结点
            if(p->lchild == nullptr)    // 前驱线索
            {
                p->lchild = pre;
                p->ltag = 1;
            } else
                p->ltag = 0;
            if(pre->rchild == nullptr)
            {
                pre->rchild = p;
                pre->rtag = 1;
            } else
                pre->rtag = 0;
            pre = p;

            Thread(p->rchild);  // 右子树线索化
        }
    }
    void ThInOrder();           // 中序线索二叉树的中序遍历
};